#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 5e6 + 10;

LL dist[N];

typedef pair<int, int> PII;
vector<PII> edges[N];
const int INF =(1<<31)-1;
LL n, m, s;
bool st[N];
void dijkstra()
{
	//初始化
	for (int i = 0;i <= n;i++) dist[i] = INF;
	//st[s] = true;//不能在这标记
	dist[s] = 0;//这一步千万不能忘

	for (int i = 1;i < n;i++)//注意这里只用跑n-1次因为我们已经知道一个节点的最短距离了
	{
		int u = 0;
		for (int j = 1;j <= n;j++)
		{
			if (!st[j] && dist[j] < dist[u]) u = j;
		}

		st[u] = true;
		for (auto& e : edges[u])
		{
			int y = e.first;int w = e.second;
			if (dist[u] + w < dist[y])
			{
				dist[y] = dist[u] + w;
			}
		}
	}
	for (int i = 1;i <= n;i++)
	{
		cout << dist[i] <<" ";
	}
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1;i <= m;i++)
	{
		int u = 0, v = 0, w = 0;
		cin >> u >> v >> w;
		edges[u].push_back({ v,w });
	}
	dijkstra();
	return 0;
}